Numerous dedicated Fourier transform implementations, including those programmed on signal processing microprocessors, have been disclosed. Most of these implementations use a variation of the Cooley-Turkey algorithm, which makes it possible to reduce the number of arithmetic operations required for computing the Fourier transform. This algorithm is well known to one skilled in the art.
In particular, the Cooley-Tukey algorithm reduces the computation of a fast Fourier transform of initial size r.sup.P into that of r Fourier transforms of size r.sup.P-1, and of supplementary complex multiplications and additions. According to the terminology customarily used by one skilled in the art, r represents the radix. Iterative repetition of this reduction produces the computation of Fourier transforms of size r. These computations can easily be carried out, especially if r is chosen equal to 2 or 4. The Cooley-Tukey algorithm uses a computation graph that takes on the appearance of a structure of a general butterfly shape, and is commonly referred to simply as a butterfly. This appearance is well known to one skilled in the art.
Several hardware architectures are possible for implementing a butterfly-shaped computation structure. A first approach includes a hardware operator capable of performing a butterfly type computation per butterfly of the graph. However, such an approach may be used only for the implementation of Fourier transforms of small size.
A second approach includes just a single hardware operator of the butterfly type, and intending to perform in succession the computations corresponding to all the butterflies of all the stages of the graph. Such an approach has the drawback of requiring a very fast hardware operator. An input memory separate from the memory is required for writing the intermediate computation results. This avoids access conflicts when a data block enters the operator while the previous block is still being processed. It is therefore necessary to provide two memories of N0 complex words, where N0 denotes the initial size of the Fourier transform. This leads to an overall circuit of considerable size, especially when N0 is large.
An intermediate approach includes a hardware operator of the butterfly type per stage of the graph, as well as a storage element. This includes delay lines or shift registers, whose function in to input the data to the operator in the right order, while aware of the butterflies of the graph of the relevant stage. Such architectures are termed serial or pipelined according to terminology well known by one skilled in the art.
More precisely, an electronic device for computing a Fourier transform having a pipelined architecture comprises a plurality of successive processing stages connected in series between the input and the output of the device by internal data paths. These stages respectively comprise processing means and storage means. The processing means performs processing operations for Fourier transforms of smaller elementary sizes than the initial size on blocks of data whose sizes are reduced in succession from one stage to the next.
The term "initial size" of the Fourier transform is understood here and in the remainder of the text to mean the size of the blocks received as input to the device by the first stage. The elementary sizes of the Fourier transforms performed by the various stages may be identical and equal to the radix of the Fourier transform; i.e., a Fourier transform with uniform radix. However, they may be different from one stage to another, as in the case of Fourier transforms with mixed radix.
Examples of pipelined architectures are described in an article by Bi and Jones, entitled "A Pipelined FFT Processor for Word-Sequential Data", IEEE Transactions on Acoustic Speech and Signal Processing, vol. 37, No. 12, December 1989, pages 1982-1985, and in an article by Bidget et al., entitled "A Fast Single-Chip Implementation of 8192 Complex Point FFT", IEEE Journal of Solid-State Circuits, vol. 30, No. 3, March 1995, pages 300-305.
The storage means described in these known architectures includes delay lines which are very simple elements to manage. They have the advantage of being generally compact, and use three transistors per stored bit. However, these elements are not always available as standard cells in ordinary libraries of components used in defining and designing integrated circuits. Furthermore, their electrical characteristics are dependent on the technology used, so that the architecture of the circuit must be carefully re-examined each time the technology advances. Such architectures use delay lines whose storage capacity per radix 4 stage is equal to 3N/2, where N is the size of the blocks processed by the stage. The architecture with delay lines, with a per-stage storage capacity equal to 3N/2, allows for processing of Fourier transforms on each symbol, while also delivering data temporally delayed by the length of a symbol, thus enabling the desired correlation to be performed.
In certain applications, especially in terrestrial applications of digital television using OFDM (Orthogonal Frequency Division Multiplex) coding for transmission, the various symbols to be processed by Fourier transforms are separated by a guard interval. More precisely, in an OFDM application, each symbol received is preceded by a guard interval which is identical to the terminal part of the symbol. In this kind of application, it is then particularly advantageous to use this property to detect the temporal position of the various symbols in the incoming flow, and thereby monitor the proper temporal synchronization of these various symbols. In this regard, a correlation of the incoming flow with the last symbol received, and its associated guard interval is generally performed. This additionally requires, in particular, the storage of a complete symbol.